/*
 * @Author: _LJP 2634716776@qq.com
 * @Date: 2024-01-29 19:52:06
 * @LastEditors: _LJP 2634716776@qq.com
 * @LastEditTime: 2024-02-01 23:57:21
 * @FilePath: /my_-linux/Pro24/Hashi/unordered/HashTable/hashTable.h
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置
 * 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */

//***************************************
//*******开散列(开链法)哈希表的实现*******
//***************************************
/*开放定址法*/

#pragma once

#include <iostream>
#include <string>
#include <vector>

template <class T>
struct HashNode {
  // 哈希表的节点设置
  typedef HashNode<T> Node;
  Node* _next = nullptr;
  T _data;

  HashNode(const T& data) : _data(data) {}
};

template <class K>
struct HashFunc {
  size_t operator()(const K& key) {
    // std::cout << key << std::endl;
    return (size_t)key;
  }
};

template <>
struct HashFunc<std::string> {
  size_t operator()(const std::string& key) {
    size_t hash = 0;
    for (auto it : key) {
      hash += it;
      hash *= 31;
    }
    // std::cout << hash << std::endl; 用于测试
    return hash;
  }
};

template <class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable;

template <class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct __Hash_Iterator {
  
  typedef HashNode<T> Node;
  typedef __Hash_Iterator<K, T, Ptr, Ref, KeyOfT, HashFunc> self;
  typedef __Hash_Iterator<K, T, T*, T&, KeyOfT, HashFunc> Iterator;
  typedef HashTable<K, T, KeyOfT> HT;

  Node* _node;
  const HT* _hashT;

  __Hash_Iterator( Node* node,  const HT* hashT)
      : _node(node), _hashT(hashT) {}//构造

  __Hash_Iterator(const Iterator& it) : _node(it._node), _hashT(it._hashT) {}//拷贝构造

  self& operator++() {
    if (_node->_next) {
      // 桶不为空
      _node = _node->_next;
    } 
    else {
      // 桶为空
      KeyOfT _kot;
      HashFunc _toint;
      size_t hashi = _toint(_kot(_node->_data))%_hashT->_hashtable.size();
      ++hashi;

      while (hashi < _hashT->_hashtable.size()) {
        if (_hashT->_hashtable[hashi]) {
          _node = _hashT->_hashtable[hashi];
          break;
        } else {
          ++hashi;
        }
      }

    if(hashi == _hashT->_hashtable.size()){
      _node = nullptr;
    }
    }
    return *this;
  }

  bool operator==(const self& s) { return _node == s._node; }

  bool operator!=(const self& s) { return _node != s._node; }

  Ptr operator->() { return &_node->_data; }

  Ref operator*() { return _node->_data; }
};

template <class K, class T, class KeyOfT, class Hash>
class HashTable {
 public:
  friend struct __Hash_Iterator<K, T, T*, T&, KeyOfT,Hash>;

  typedef __Hash_Iterator<K, T, T*,T&, KeyOfT, Hash> iterator;
  typedef __Hash_Iterator<K, T, const T*, const T&, KeyOfT, Hash> const_iterator;

  iterator begin() {

    Node* cur = nullptr;

    for (size_t i = 0; i < _hashtable.size(); ++i) {
      cur = _hashtable[i];
    
      if (cur) {
        break;
      }
    }
    return iterator(cur, this);
  }

  iterator end() { return iterator(nullptr, this); }

  const_iterator begin()const {
    Node* cur = nullptr;

    for (size_t i = 0; i < _hashtable.size(); ++i) {
      cur = _hashtable[i];

      if (cur) {
        break;
      }
    }
    return iterator(cur, this);
  }

  const_iterator end()const { return iterator(nullptr, this); }

  typedef HashNode<T> Node;
  KeyOfT kot;

  std::pair<iterator,bool> Insert(const T& data) {//插入函数
    Hash to_int;

    // 使用Find函数进行判断是否需要进行插入(需要预防除零错误)
    iterator it = Find(kot(data));
     if (it != end()) {
      // 找到该数据说明该数据存在不予继续插入
      return {it, false};
    }

    if (_n == _hashtable.size()) {
      // 判断负载因子是否为1 负载因子若是为1则进行扩容
      //   size_t newsize = _hashtable.size() == 0 ? 10 : _hashtable.size() *
      //   2;
      size_t newsize = GetNextPrime(_hashtable.size());
      std::vector<Node*> newTable(newsize,nullptr);

      // for(Node *&cur : _hashtable) 遍历Node*指针数组
      for (auto& cur : _hashtable) {
        while (cur) {
          Node* next = cur->_next;
          size_t hashi = to_int(kot(cur->_data)) % newTable.size();
          cur->_next = newTable[hashi];
          newTable[hashi] = cur;
          cur = next;
        }
      }
      _hashtable.swap(newTable);
    }

    // 正常插入
    Node* newnode = new Node(data);
    size_t hashi = to_int(kot(data)) % _hashtable.size();
    newnode->_next = _hashtable[hashi];
    _hashtable[hashi] = newnode;
    ++_n;
    return {iterator(newnode,this),true};
  }

  iterator Find(const K& key) {
    Hash to_int;

    if (_hashtable.size() == 0) return iterator(nullptr,this);  // 防止除零错误

    size_t hashi = to_int(key) % _hashtable.size();
    Node* cur = _hashtable[hashi];

    while (cur) {
      if (kot(cur->_data) == key) {
        return iterator(cur, this);
      }
      cur = cur->_next;
    }
    return end();
  }

  iterator Erase(const K& key) {
    Hash to_int;
    if (_hashtable.size() == 0) return iterator(nullptr,this);  // 防止空的情况继续删除

    size_t hashi = to_int(key) % _hashtable.size();

    Node* cur = _hashtable[hashi];
    Node* prev = nullptr;
    while (cur) {
      if (kot(cur->_data) == key) {
        if (prev) {
          prev->_next = cur->_next;
        } else {
          _hashtable[hashi] = cur->_next;
        }
        delete cur;
        return iterator(_hashtable[hashi],this);
      } else {
        prev = cur;
        cur = cur->_next;
      }
    }
    return iterator(nullptr, this);
  }

 protected:
  size_t GetNextPrime(size_t prime) {
    static const int __stl_num_primes = 28;
    static const unsigned long __stl_prime_list[__stl_num_primes] = {
        53,        97,         193,        389,       769,       1543,
        3079,      6151,       12289,      24593,     49157,     98317,
        196613,    393241,     786433,     1572869,   3145739,   6291469,
        12582917,  25165843,   50331653,   100663319, 201326611, 402653189,
        805306457, 1610612741, 3221225473, 4294967291};
    size_t i = 0;
    for (; i < __stl_num_primes; ++i) {
      if (__stl_prime_list[i] > prime) return __stl_prime_list[i];
    }
    return __stl_prime_list[i];
  }

 private:
  std::vector<Node*> _hashtable;  // 哈希表整体构造
  size_t _n = 0;                  // 负载因子
};
